弱隔离性与分布式（Weak Isolation and Distribution）
由 Peter Bailis 介绍
被选中的读物
Atul Adya, Barbara Liskov, and Patrick O’Neil. Generalized Isolation Level Definitions. ICDE, 2000.
Eric Brewer. CAP Twelve Years Later: How the ”Rules” Have Changed. IEEE Computer, 45, 2 (2012).
传统的数据库智慧认为可串行化事务是并发编程的规范解决方案，然而这个观点，鲜少在真实世界成立。在实践中，绝大多数的数据库系统将会实现非可串行化的事务，使得它们的用户所执行的事务，可能并不放在一些串行化的事务序列下面执行。在这篇文章之中，我们将会讨论，为什么这个被称为“弱隔离性”（weak isolation）的策略被如此广泛地传播与应用，而这些非可串行化的隔离模式究竟真正干了些什么，以及为什么可串行化难以落地的真正原因。
对历史的回顾以及流行的原因
即使在早期的数据库系统之中（请查看第三章），数据库系统的设计者们也都意识到，实现可串行化的代价是如此昂贵。而让事务似乎像是一个按照序列执行的这样的一个要求，对于数据库中事务的实现，发挥了相当深远的影响。如果事务，访问数据库中并不相关的数据项，可串行化的实际代价就是“无”：在这些互不相交的访问模式之下，一个可串行化的调度安排允许数据的并行运行。不过，如果事务在相同的数据项目上面竞争，在最差劲的情况下面，系统将会无法使得它们在任何的并行运行环境下面执行。对于客串行化而言，这项属性是如此的基本，和独立于所有的实现方案：因为事务并不能安全地让所有的工作负载在所有的工作流下面成立（也就是说，它们必须协调起来工作），而任何可串行化的可能实现，在实际上来说，要求序列化的执行。在实践中，这就意味着事务可能需要等待，在增加延迟的同时，对于吞吐量展开削减。事务处理专家 Phil Bernstein 认为，与最常见的一种被称呼为“读已提交”的隔离级别[^13]相对比，可串行化往往会造成三倍级别的性能损失。这就往往取决于实现，可串行化可能同样会引发更多的终止，事务的重启，以及/或者死锁。而在分布式的数据库之中，因为网络之间的通信开支是如此昂贵，以至于这些开销增长如此之大，由此也就让执行可串行化的事务的所需时间增长地很多（比如，持有锁的时间）；我们也已经观察到，在不利的条件下面，性能会遭遇多个数量级的下跌[^7]。
作为得出来的结论，数据库系统设计者们从使用可串行化转向使用一些隔离性相对弱一些的模型（weaker models）来实现事务。在弱隔离性的模型下面，事务并不被鼓励表现出可串行化的行为。与之相对的，事务将会表现出一定范围内的异常的情况（或者“现象”）：这些行为绝不可能出现在可串行化的执行序列下面。而真实的异常，取决于哪一种模型将会被提供出来，而常见的一些异常的现象，包括读取到了一些尚且在由其它事务生成构建出来的中间数据，读取到了被终止的事务，所产生出来的数据，在同一个事务，相同的数据项内，读取到了两个以及更多的不同内容的数据，或者因为一些并发的事务向相同的数据列写入了数据，丢失（“losing”）了一些由当前事务所带来的影响（对应的几个名词，就是脏读，幻读，和不可重复读，译者注）。
这些弱化了的隔离模式，实际上流行地令人惊讶。在最近展开的一十八项SQL与“新时代SQL”（NewSQL）的调查之中[^5]，我们发现，十八个项目中，只有三个数据库项目，在默认情况下面，选择了可串行化的级别，而另外的八个（包括 Oracle 和 SAP 的 旗舰产品）甚至完全没有提供可串行化隔离级别！由于对于术语的使用，往往并不是非常精确，这种状态实际上，变得复杂化了：举例来说，Oracle 的“可串行化”隔离级别，提供的实际上是快照隔离级别（Snapshot Isolation），这是一种弱化了的隔离级别[^15]。同样的，在不同的商业容器提供者之间，存在着类似的冲突。简单来说，当供应商A，一个事务处理市场中的主要玩家，选择将其默认的隔离级别，从可串行化，转变为读已提交，而供应商B，它依旧默认选择着可串行化，那么这种情况下，它在销售合同上面的竞争，就会居于供应商A的下风。因为供应商B的数据库很明显地，工作效率不如供应商A的数据库，那么从消费者的视角来看，我们为什么选择供应商B的数据库，而不是供应商A的数据库？毫不意外地，供应商B同样把自家数据库的隔离级别，配置为读已提交。
核心的挑战：关于异常所产生的原因
一项主要的关于为什么弱隔离级别总是困难重重的原因在于，依靠于应用程序，弱隔离级别的异常现象，可能导致应用程序级别的不可持续性：每一个在可串行化下由各个事务持有的不变状态量，在弱隔离级别下面，可能就会发生改变（也就是存在被篡改的可能，译者注）。举例来说，如果两个用户，尝试在相同的时间，尝试从银行取走资金，而它们的事务，恰好就运行于允许同时并发写入相同的数据项目的弱隔离级别之下（比如，一半的读已提交模型），那么用户，就有可能顺利从银行账户中，取走比账户持有的更多的资金量（这种情况下面，每一个事务，同时读取着相同的账户，同时计算着根据取走的资金量，账户中的余额，最后同时向数据库写入“崭新的”数据）。而这可不是什么虚幻的场景。就在最近所发生的一个生动的案例，一名攻击者，就系统化地利用了 Flexcoin 比特币交易系统的弱隔离模型的弱点；通过在 Flexcoin 应用程序之中，用编程的方式，不断触发交易系统的非事务性读-修订-写的行为（这实际上是一个在读已提交隔离级别，以及一种更为复杂的访问模式，即快照隔离模式之下的漏洞），这名攻击者取走了比她本应持有的更多的比特币，最终使得交易系统破产[^1]。
也许，这非常让人惊讶，只有少数与我所沟通的开发者，能够真正意识到，他们所应用的事务实际上处于非可串行化隔离级别下面。实际上，在我们的研究之中，我们已经发现，许多开源的ORM后端应用程序，假定他们的事务，工作于可串行化隔离级别下面，这就使得，在商用数据库引擎上面部署的时候，一系列可能的应用程序数据完整性冲突[^6]。而那些对于弱隔离性清除的研究者们，转向于那些在应用程序级别，可用于代替隔离级别的一些科技，比如不同粒度的锁（比如，SQL 中的“SELECT FOR UPDATE”），以及引入假性冲突，（比如，在快照隔离级别下面，写入一把假锁）。这些做法，非常容易引发错误，同时使得许多事务当中的优良概念，化为虚无。
不幸的事情在于，在弱隔离级别下面，他们的规范性，往往并不完整，模棱两可，甚至并不准确。而这些规范，有着可以追溯到1970年代的，悠久的历史。而即使它们已经在随后的历程中做出来了改进，它们依旧问题重重。
最为早期的弱隔离模式，是在操作上被指定的：正如我们在第三篇章所看到的那样，诸如读已提交那样的流行模型，最初是通过修订读锁的持有时间，而被研究出来的[^17]。所以对于读已提交的定义就是：“在短的期间内，持有一把读锁，同时在一个较长的时间段内，持有写锁”（“hold read locks for a short duration, and hold write locks for a long duration.”）。
而随后提出的 SQL ANSI标准，则尝试提供一个与具体实现无关的对于多种弱隔离模型的描述，这就不仅仅涉及到了基于锁的机制，还牵扯到了基于多个版本的，以及乐观模式。不过，正如 Gray 等人在[^11]所叙述的那样，SQL 的标准非常模棱两可，同时没有细化： 对于英语文本描述的解读，存在多种可行的解读，同时它们的规范化，并没有捕捉到所有基于锁的实现的行为：举例来说，在 Gray 等人在他们1995年的论文发表出来之前，SQL ANSI 标准并没有牵涉到所有的隔离模式：举例来说，供应商们，已经开始在它们的商业数据库产品中，提供快照隔离模式（然后标榜，这就是可串行化！）（不幸的事情在于，直到2015年，SQL的ANSI标准依旧没有发生变化）。
而更为复杂的事情在于，Gray 等人在1995年重新审阅发现，规范化一样 是问题重重：它们围绕着锁相关的语义，同时忽略了在多版本并发事务控制下面的一些值得考虑的安全问题。紧随其后的，在他1999年的博士论文中[^2]，Atul Adya 向弱隔离性中引入了我们所期待的最好的规范。Adya的论文，修订了多版本可串行化图中围绕弱隔离模型的形式化定义[^12]，同时将这些图中的异常现象与严格限制，描述了出来。我们收录了 Adya 在 ICDE 2000 所提出来的对应文章，但是那些对于隔离性感兴趣的人，应当去阅读完整的文本。不幸的事情在于，Adya 的模型，依旧没能说明某些边界条件下的情况（比如，如果不涉及读取行为，G0究竟意味着什么？），并且这些保证的具体实现，在不同的数据库下面，各有其区别与差异。
而即使有着最为完美的规格，弱隔离性因为其缘由，依旧是一个现实当中的挑战。为了判断弱隔离级别是否“安全”，编码人员们，必须手动将它们应用程序级别的持续性的概念，落地到更为基层的读取以及写入行为上面[^3]。这实际上相当艰难，即使对于那些身经百战的数据库事务控制专家而言，同样也是如此。实际上，一种可能的视角就是，如果可串行化受到损害，那么事务的好处，究竟还有什么？而读已提交隔离级别相较于没有隔离级别为什么是一件更为容易的事情？而对于那些类似于Oracle的工作于弱隔离级别的数据库引擎， 它们内部的组织结构，又是如何运作的？ --- 无论用户是在预定航班，预订酒店还是说做股票交易？而这些情况，文献中提出的线索相当少，这使得当前实践中，那些部署的交易成功的概念，存在着严重的问题。
而我所遇到的，为什么在实践中，弱隔离性似乎在实践中“可行”的最有说服力的论据在于，在今天，只有少数应用程序，依旧在应用着高并发控制级别。而如果没有了并发，绝大多数弱隔离性的实现，依旧可以拿出可串行化的结果来。而这也引申出了很多丰富多彩的研究成功。即使在分布式的配置之中，弱的隔离性数据库，依旧传递着“一致性的”结果：举例来说，在 Facebook 上面，只有大约 0.0004% 从最终一致性的商店中返回来的结果被“偷窃”[^19]，而其它的一些机构，也得出来了类似于的结论[^10]，[^25]。不过，对于许多应用程序而言，弱隔离性实际上很可能并不是一个问题，它可以是：就如同我们的 Flexcoin 的案例中所说明的那样，它实际上是一组错误可能性的整合，应用程序的作者们，在处理（或者选择性忽略）与并发相关的异常的时候，必须谦恭戒惧。
弱隔离性，分布式，以及“NoSQL”
伴随着互联网伸缩性服务的不断涌现，以及云计算的兴起，弱隔离性正在变得日益流行。正如我在早期所提到的那样，分布式加剧了可串行化的开销，以及，在分区系统的错误事件阶段（比如，服务的崩溃），事务可能会陷入无限期的搁置之中。而越来越多的编码人员们，则开始编写分布式的应用程序，同时使用分布式的数据库，这些概念开始成为主流。
而在过去的十年之中，我们可以看到，许许多多的新的数据存储优化开始被应用到分布式的环境之中，它们被合称为“NoSQL”。而"NoSQL"这个标签，很不幸地是超载了的，同时它被很多这方面的存储领域所引 用，从欠缺对 SQL 的支持，到简化了的数据模型（比如，key-value 键值对），到缺乏事务方面的支持。而到了今天，正如像 MapReduce 那样的系统那样（第五章），NoSQL 存储同样添加了这些特性进来。不过，一个值得注意的，基本的差异在于，这些 NoSQL 存储更多地聚焦于，在弱隔离性模型上面，提供更好的可用的操作符，同时它们明确关心容错性（而有点讽刺的地方在于，NoSQL 存储一般情况下，是和那些不可串行化的承诺相关联在一起的，然而经典的关系型数据库，并不在默认的情况下面，提供可串行化能力）。
作为这些 NoSQL 存储的一则案例，我们收录了来自于亚马逊公司，围绕 Dynamo 系统而撰写的一篇发表于 SOSP 2007 上面的文章。Dyname 被引入为亚马逊的商品交易系统，提供高可用性与低延迟性。从技术角度来看的话，这篇文章非常有趣，因为它牵涉到了很多不同的方面，包括 quorum 复制，Merkle 树的反熵问题，一致性哈希，以及版本向量。这个系统从整体来看，是非事务性的，同时并不提供任何的原子操作（比如，比较与交换），同时需要应用程序的研究者们，去协调各种具有分歧的更新。在这重重限制之下，所有的节点可以更新任何数据项目（在不同节点的切换之下，hinted handoff）。
通过使用 merge 函数，Dynamo 修订了 "乐观复制优化"政策：首先我们将接收写入数据的请求，稍后再协调不同的版本[^21]，[^16]。同时在另外一面，预先发送一组不同版本的数据给用户，在读已提交隔离级别中，相较于简单地抛弃一些并发的更新，往往更加友好。而到了另外一个方面，一名程序编码人员，必须对 merge 函数展开调查研究。这就激发起了许多的疑问：对于应用程序而言，怎样的合并算是好的合并？我们如何避免抛弃一些已经提交了的数据？如果一则操作在一开始，就不应当并发执行，那么我们需要展开怎样的操作？一些开源版本 Dynamo 的复刻版本，如 Apache 的 Cassandra，并不接受 merge 的操作，而是简单地通过数字序列化的时间戳，选择“成功”写入（"winning" wirte）战略。另外一个角度来看，就像 Basho Riak 所体现的那样，它们采用了可以自动合并诸如计数器那样的数据类型的“库”，这就是交换式复制数据类型[^22]。
Dynamo 同样不对于读的最新性做出任何的保证。与之相对的，它将会保证，如果写入停止，最终所有的数据复制项都将会包含相同的写入内容集合。这种最终一致性实际上就是一种标志性的弱一致性保证：从技术上面看，最终一致性的数据存储，将会在一段无限拖延的时间之后，返回泄露了的（甚至是垃圾）数据[^9]。而在实践中，数据存储依赖模块们，往往能够返回最近的数据[^25]，[^10]，但是，用户依旧需要就不可串行化的行为，展开调查研究。更进一步的事情在于，在实践中，许许多多的存储提供一种被称为“会话保证”（session guarantees）的中间隔离形式，它们可以确保用户能够读取到他们自己的写入（而并不是其它用户的写入）；有趣的事情在于，这些科学技术，在 1990年代的早期在 Bayou 项目的移动设备计算领域，就已经研究了出来，而到了最近，他们再次崭露头角[^23]，[^24]。
权衡与 CAP 理论
我们的这组文章之中，也同样收录了 Brewer 的对于 CAP 理论 的一十二年回顾文章。最初，Brewer的CAP理论最初是在他构建 Inktomi，最早的可伸缩性搜索引擎的时候，跑出来的，它简单地阐述了协调（或者“可用性”）与类似于可序列化的强保证之间的平衡关系。虽然早期的结果，就描述了这种权衡[^14],[^18]，CAP 也成为了2000年代中期，开发者们的口号，并且产生了相当巨大的影响。Brewer 的文章简单地讨论了由 CAP 所带来的性能影响，以及在不依赖于协调的情况下，保持一些一致性标准的可能性。
可编程能力与实践
正如同我们所见过的那样，弱隔离级别是一个相当契合实际的挑战：它的性能与可用性优势意味着，尽管我们对其所知甚少，但是它依旧在开发者群体当中，大受欢迎！即使有着完美的规范，但是对于弱隔离性模型的推导，依旧是一个相当艰难的问题。为了判断出哪一种弱隔离性是“安全”的，程序员们，必须从手动将他们的应用程序级别的一致性观念，下推到低层次的读与写的行为上面[^3]。这实际上非常艰难，即使对于那些身经百战的并发控制专家而言，也是如此。
而由此，我非常相信，对于语义的讨论，必将有一个重大的机遇，这些语义，并不会受着性能与可用性负载的影响，而且他们将会比现有的东西，更加直观，更加可用，以及更加具有可编程性。弱隔离性从历史上面看，非常难以推理，但是从现实来看，情况并非如此。我们，与其它的同志们，已经发现了很多具有极高含金量的用例，包 括索引，以及视图的维护，以及一致性的维护，以及分布式的聚合函数，它们在很多时候，并不真正需要协调就可以产生“正确的“行为；因此，对于这些用例，可串行化实际上依旧是做了过度的保护[^4],[^8],[^20],[^22]。这也就是说，通过向数据库应用程序，提供有关应用程序的额外知识，数据库的用户们可以各地其所，各展其才。而更进一步，挖掘这些用例，则是一个更为成熟的研究领域。
结论
简单来说，弱隔离性模型因为它的许多好处而得以流行：更少的协调，更高的性能，以及更好的可用性。不过，即使是在学术环境下面，它的语义，它的风险，以及使用案例依旧是难以理解。考虑到对于可串行化事务的大量研究，这件事情依旧是令人困惑，尽管很多人认为，它是一个“已经被解决的问题”。弱隔离性模型可以说已经经过了彻彻底底地研究之后。正如我所强调的那样，许多的挑战依旧是存在的：现代的系统如何工作，以及用户程序员们如何来处理弱隔离模型？对于当下，我提出如下一些解决的思路方针：
- 不可序列化的隔离模型，得益于其与并发控制相关的好处，如今在实践中已经相当流行（同时在经典的关系型数据库以及最近的NoSQL数据库中）
- 尽管流行，但是许多，目前存在着的不可串行化隔离性模型的规范，依旧是含糊不清，并且难以应用
- 对于新的形式的弱隔离性模型的研究证明了如何在不牺牲可串行性的情况下，保留有意义的语义，并且改善可编程性
参考
[1] Flexcoin: The Bitcoin Bank, 2014. http://www.flexcoin.com/; originally via Emin G¨un Sirer.
[2] A. Adya. Weak consistency: a generalized theory and optimistic implementations for distributed transactions. PhD thesis,
MIT, 1999.
[3] P. Alvaro, P. Bailis, N. Conway, and J. M. Hellerstein. Consistency without borders. In SoCC, 2013.
[4] P. Bailis. Coordination avoidance in distributed databases. PhD thesis, University of California at Berkeley, 2015.
[5] P. Bailis, A. Davidson, A. Fekete, A. Ghodsi, J. M. Hellerstein, and I. Stoica. Highly Available Transactions: Virtues and
limitations. In VLDB, 2014.
[6] P. Bailis, A. Fekete, M. J. Franklin, A. Ghodsi, J. M. Hellerstein, and I. Stoica. Feral Concurrency Control: An empirical
investigation of modern application integrity. In SIGMOD, 2015.
[7] P. Bailis, A. Fekete, M. J. Franklin, J. M. Hellerstein, A. Ghodsi, and I. Stoica. Coordination avoidance in database
systems. In VLDB, 2015.
[8] P. Bailis, A. Fekete, A. Ghodsi, J. M. Hellerstein, and I. Stoica. Scalable atomic visibility with RAMP transactions. In
SIGMOD, 2014.
[9] P. Bailis and A. Ghodsi. Eventual consistency today: Limitations, extensions, and beyond. ACM Queue, 11(3), 2013.
[10] P. Bailis, S. Venkataraman, M. J. Franklin, J. M. Hellerstein, and I. Stoica. Probabilistically Bounded Staleness for
practical partial quorums. In VLDB, 2012.
[11] H. Berenson, P. Bernstein, J. Gray, J. Melton, E. O’Neil, and P. O’Neil. A critique of ANSI SQL isolation levels. In
SIGMOD, 1995.
[12] P. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency control and recovery in database systems, volume 370.
Addison-Wesley New York, 1987.
[13] P. A. Bernstein and S. Das. Rethinking eventual consistency. In SIGMOD, 2013.
[14] S. Davidson, H. Garcia-Molina, and D. Skeen. Consistency in partitioned networks. ACM CSUR, 17(3):341–370, 1985.
[15] A. Fekete, D. Liarokapis, E. O’Neil, P. O’Neil, and D. Shasha. Making snapshot isolation serializable. ACM TODS,
30(2):492–528, June 2005.
[16] J. Gray, P. Helland, P. ONeil, and D. Shasha. The dangers of replication and a solution. In SIGMOD, 1996.
[17] J. Gray, R. Lorie, G. Putzolu, and I. Traiger. Granularity of locks and degrees of consistency in a shared data base.
Technical report, IBM, 1976.
[18] P. R. Johnson and R. H. Thomas. Rfc 667: The maintenance of duplicate databases. Technical report, 1 1975.
[19] H. Lu, K. Veeraraghavan, P. Ajoux, J. Hunt, Y. J. Song, W. Tobagus, S. Kumar, and W. Lloyd. Existential consistency:
measuring and understanding consistency at Facebook. In SOSP, 2015.
[20] S. Roy, L. Kot, G. Bender, B. Ding, H. Hojjat, C. Koch, N. Foster, and J. Gehrke. The homeostasis protocol: Avoiding
transaction coordination through program analysis. In SIGMOD, 2015.
[21] Y. Saito and M. Shapiro. Optimistic replication. ACM Comput. Surv., 37(1), Mar. 2005.
[22] M. Shapiro, N. Preguica, C. Baquero, and M. Zawirski. A comprehensive study of convergent and commutative replicated
data types. INRIA TR 7506, 2011.
[23] D. Terry. Replicated data consistency explained through baseball. Communications of the ACM, 56(12):82–89, 2013.
[24] D. B. Terry, A. J. Demers, K. Petersen, M. J. Spreitzer, M. M. Theimer, et al. Session guarantees for weakly consistent
replicated data. In PDIS, 1994.
[25] H. Wada, A. Fekete, L. Zhao, K. Lee, and A. Liu. Data consistency properties and the trade-offs in commercial cloud
storage: the consumers’ perspective. In CIDR, 2011.